package ViolenceRecursive;

/**
 * 按照1-a,2-b,...,26-z 的对应关系转换数字和字母，一个有多少种转换方式
 *
 * @author Liaorun
 */
public class ConvertToLetterString {


    // 问：为什么结果大于1？
    // 答：是在遇到1和2的时候有两种对应情况，将两种对应情况加起来，结果就会大于1

    public static void main(String[] args) {
        System.out.println(number("111"));
    }


    public static int number(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }

        return process(str.toCharArray(), 0);
    }

    /**
     * @param chars 需要转化为字母的数字数组
     * @param i     之前的位置，转化已经做过决定了
     * @return i 位置后面有多少种转化结果
     */
    private static int process(char[] chars, int i) {
        // base case
        if (i == chars.length) {
            // 成功转换了所有的数字，这个一个成功的尝试，返回1
            return 1;
        }

        if (chars[i] == '0') {
            // 不是一个合法的尝试，返回0
            return 0;
        }

        if (chars[i] == '1') {
            // i自己作为单独的部分，后续有多少种方法
            int res = process(chars, i + 1);

            if (i + 1 < chars.length) {
                // i和i+1作为单独的部分，后续有多少种方法
                res += process(chars, i + 2);
            }

            return res;
        }

        if (chars[i] == '2') {

            // i自己作为单独的部分，后续有多少种方法
            int res = process(chars, i + 1);

            // 有下一位且 在 i+1位置的数在[0,6]范围
            if (i + 1 < chars.length && (chars[i + 1] >= '0' && chars[i + 1] <= '6')) {
                // i和i+1作为单独的部分，后续有多少种方法
                res += process(chars, i + 2);
            }

            return res;
        }

        return process(chars, i + 1);
    }


    /**
     * 动态规划版本，所有的暴力尝试都可以改成动态规划
     *
     * @param num
     * @return
     */
    public static int dpWays(int num) {
        if (num < 1) {
            return 0;
        }

        char[] str = String.valueOf(num).toCharArray();

        int n = str.length;

        // 为什么是n+1,应为递归可以取到这个返回值为1
        int[] dp = new int[n + 1];

        // 根据递归base case确定dp[n] = 1;
        dp[n] = 1;
        dp[n - 1] = str[n - 1] == '0' ? 0 : 1;

        // 从base case 向前推，计算第0个位置有多少转化方式
        for (int i = n - 2; i > 0; i--) {
            if (str[i] == '0') {
                // 遇到0是不能转化的
                dp[i] = 0;
            } else {
                // 每增加一种转化方式，排列组合的结果就为 1 * 右侧的组合方式
                dp[i] = dp[i + 1] + (((str[i] - '0') * 10 + str[i + 1] - '0') < 27 ? dp[i + 2] : 0);
            }
        }

        return dp[0];
    }
}
